class Solution
{
public:
    int beautifulSubsets(vector<int> &nums, int k)
    {
        unordered_map<int, vector<int>> groups;
        sort(nums.begin(), nums.end());

        // 按余数分组，每个组内暴力枚举，每个组 O(2^n)
        // 极限情况下只分出一个组将不能降低复杂度。实际用例可能没有覆盖到，能过
        for (int num : nums)
        {
            groups[num % k].push_back(num / k);
        }
        int result = 1;
        for (auto &[mod, group] : groups)
        {
            int groupSize = group.size();
            int count = 0;
            for (int mask = 1; mask <= ((1 << groupSize) - 1); ++mask)
            {
                bool isBeautiful = true;
                int last = -2;
                for (int i = 0; i < groupSize; ++i)
                {
                    if (mask & (1 << i))
                    {
                        if (group[i] - last == 1)
                        {
                            isBeautiful = false;
                            break;
                        }
                        last = group[i];
                    }
                }
                if (isBeautiful)
                {
                    ++count;
                }
            }
            result *= count + 1;
        }
        return result - 1;
    }

    // 直接暴力，超时
    int beautifulSubsets(vector<int> &nums, int k)
    {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int mask = 1; mask <= ((1 << n) - 1); ++mask)
        {
            bool isBeautiful = true;
            vector<bool> exist(1001, false);
            for (int i = 0; i < n; ++i)
            {
                if (mask & (1 << i))
                {

                    if (nums[i] >= k && exist[nums[i] - k])
                    {
                        isBeautiful = false;
                        break;
                    }
                    exist[nums[i]] = true;
                }
            }
            if (isBeautiful)
            {
                ++count;
            }
        }
        return count;
    }
};